//支配集，独立集，覆盖集与团介绍
//domination_independent_covering_clique_introduction.cpp

//介绍图论中的支配集，独立集，覆盖集与团

//网络上各种文档中关于二分图，匹配，支配集，独立集，覆盖集这些概念的资料很多
//但它们对这些概念和定理的解释含糊不清，定义不明确
//不同文档之间的概念与定理的解释甚至相互冲突，矛盾
//所以本文专门对这些概念进行统一的讲解，防止读者受到错误的指导
//本文所有概念与定理都以“图论讲义 第5章”(支配集，独立集，覆盖集与团)为准
//关于这些概念的问题大多是NP完全问题，但应用于二分图时可以用一些复杂度较低的算法求解
//事实上竞赛中这类问题多是与二分图联系起来的
//
//支配集，独立集，覆盖集等等这些概念适用于所有图，并非只是二分图
//在图G=<V,E>中，V是节点集合，E是边集合
//1)支配集(Domination Set)
//支配集：V的一个节点子集D，对于V中所有节点i，它要么属于D，要么是D中节点的邻节点
//极小支配集：其任何真子集都再不是支配集，即再减少任何节点都不再是支配集的支配集
//最小支配集：节点数量最少的支配集
//支配数：最小支配集的节点数量
//支配集的性质：
//最小支配集必然是极小支配集，反之却不然
//二分图B=<X,Y,E>中X和Y集合都是支配集
//若图G有一完备匹配M，则从M中每条边取一个节点组成的节点子集是一个支配集
//
//2)点独立集(Vertex Independent Set)
//点独立集：V的一个节点子集，其中任意两节点都不相邻
//极大点独立集：其任何超集都不再是点独立集，即再加任何节点都不再是点独立集的点独立集
//最大点独立集：节点数量最多的点独立集
//独立数：最大点独立集的节点数量
//独立集与支配集的关系：
//图G的极大独立集必然是它的极小支配集，反之则不一定成立
//一个独立集是极大独立集当且仅当它是支配集
//
//3)点覆盖(Vertex Covering Set)
//点覆盖：V的一个节点子集，图G中所有边至少有一个端点属于该节点子集
//极小点覆盖：其任何真子集都不再是点覆盖，即再减少任何节点都不再是点覆盖的点覆盖
//最小点覆盖：节点数量最少的点覆盖
//点覆盖数：最小点覆盖的节点数量
//点覆盖的性质：
//最小点覆盖必然是极小点覆盖，反之却不然
//在连通图中，点覆盖必然是支配集，反之支配集却未必是点覆盖
//(点)独立数 + 点覆盖数 = 图G的节点总数
//即最小独立集的节点数 + 最小点覆盖的节点数 = 图G的节点数
//很多中文文档都将点覆盖数简称作覆盖数，不过并不准确
//
//4)团(Clique)
//团：V的一个节点子集以及该节点子集中所有节点之间的边所组成的子图
//若该子图是完全子图，则导出子图的该节点子集是一个团
//极大团：其任何超集都不再是团，即再加入任何节点都不再是团的团
//最大团：节点数量最多的团
//团数：最大团的节点数量
//
//5)边独立集
//边独立集：匹配即为边独立集
//一般提到独立集是指点独立集，而匹配则是专指边独立集这个概念
//最大边独立集：最大匹配
//边独立数：匹配数
//匹配的性质：
//简单无环图G中的匹配数 <= 点覆盖数，即最大匹配节点数<=最小点覆盖节点数
//Konig定理(o字母上有两点)：二分图B的匹配数 = 点覆盖数
//即最大匹配节点数=最小点覆盖节点数，一般写作最大匹配数=最小覆盖数
//
//6)边覆盖
//边覆盖：E的一个边的子集，图G中所有节点都至少与该子集中一条边相关联，即为其端点
//极小边覆盖：其任何真子集都不再是边覆盖，即再减去任何一条边都不再是边覆盖的边覆盖
//最小边覆盖：边的数量最少的边覆盖
//边覆盖数：最小边覆盖的边数量
//边覆盖与匹配(边独立集)的关系：
//Gallai定理：若图G是连通图，则匹配数 + 边覆盖数 = 节点总数
//Gallai推论1：若图G的任一匹配M和任一边覆盖L满足|M|<=|L|
//等号成立时M为完备匹配且L为最小边覆盖
//Gallai推论2：若图G的任一匹配M和任一点覆盖C满足|M|<=|C|
//等号成立时M为最大匹配且C为最小点覆盖
//Gallai推论3：若图G的任一点独立集I和任一边覆盖L满足|I|<=|L|
//等号成立时I为最大点独立集且L为最小边覆盖
//将Gallai定理及推论应用于二分图时可以得到相应的性质
//推论：若图G是连通图，则有
//匹配数 <= 边覆盖数，等号成立当且仅当图G有完备匹配
//匹配数 <= 点覆盖数
//点独立数 <= 边覆盖数
//推论：二分图B的点独立数 = 边覆盖数
//
//7)总结
//无环简单图G中：
//(最大点)独立数 + (最小点)覆盖数 = 节点总数
//匹配数(也称边独立数) <= (最小点)覆盖数
//二分图B中：
//(最大)匹配数 = (最小点)覆盖数
//(最大点)独立数 = (最小)边覆盖数
//二分图B结合无环简单图的性质也有：
//(最小)边覆盖数 + (最小点)覆盖数 = 节点总数
//(最小)边覆盖数 + (最大)匹配数(也称边独立数) = 节点总数
//
//以上就是二分图与匹配，独立集，覆盖集相关概念中常见的六条公式
